1. Field of Invention
This invention relates to an addressing environment storage and more particularly to such a storage employed in accessing data items arranged in pushdown stacks which are stored in a computer memory.
2. Description of the Prior Art
Most computer systems made to this day are of the conventional von Neumann organization which has remained relatively unstructured with the objective of being "general purpose". However, over the past two decades, better understanding has been achieved in the exploitation of the potential of block-structured programming languages tat represent complex algorithms. Block structuring of algorithms, i.e., nested declarations, is a natural form for the expression of such complex algorithms.
A particular computer system that was desigred to employ such block-structured, or nested languages, (and also nested data structures) is described in the Barton, et al., U.S. Pat. Nos. 3,461,434; 3,546,677 and 3,548,384. These patents escribe a stack-oriented data processor where the stack mechanism, a first-in last-cut mechanism, handles the flow of operators and associated parameters in a manner which reflects the nested structure of particular higher level languages that are designed to handle natural forms for the expression of complex algorithms. Such languages include ALGOL and ALGOL type languages, such as PL/1, EULER, and so forth, which are based on the block-structuring of algorithms, i.e., nested declarations. While this may appear to impose unnecessary constraints on system development, the resulting products, measured in terms of throughput and flexibility, suggest that design "constraints" may really have been design opportunities (Cf., E. I. Organick, Computer System Organization, Academic Press 1973).
A system of the type described in the above-identified Barton patents is oriented around the concept of a segmented memory and specially treated segments called stacks. The processor runs in an expression stack; operators take their arguments from the top of the stack and leave their results on the top of the stack. The data addressing space of the executing program is mapped into the stack as well as other stacks linked to it and data seents referenced by descriptors contained in the stack structure.
The addressing environment of the executing code stream consists of a set of local addressing spaces contained within the stacks. These are called activation records or lexical regions and each consists of a set of variables addressed by an index relative to the base of the activation record. That is to say, addressing of a given data item is by way of an address couple of the form (Lambda, Delta), where Lambda is lexical level of a given activation record in the stack and Delta is the offset to the variable from the base of the activation record at level Lambda. In order to access any activation record within a stack, the respective records, or lexical regions, are linked together by pointers from the base of the topmost activation record to the lowest level activation record. In the above-described Barton patents, addressing is optimized by defining an array of "display" registers maintained in such a manner that element i in the array contains the base of the activation record at level i. This allows quicker access to any of the display values or addresses to the base of any particular activation record and is much quicker than evaluating links by following links from the top activation record down to activation record i.
Activation records are created by executing a procedure entry operator and deleted by executing a procedure exit operator. Both operators may cause a change in the addresses of the various activation records and thus require that the display buffer be updated, which may take a non-trivial amount of time to do.
It is then, an object of the present invention to provide an improved address environment mechanism for addressing various variables stored in stacks in a computer memory, by maintaining multiple sets of display registers.
It is still another object of the present invention to provide such an addressing environment mechanism where changes in the make-up of a given stack may be made and a set of display registers updated without taking an inordinate amount of time.
It is still a further object of the present invention to provide such an addressing environment mechanism where a deleted set of display registers may be reused at a future time with the absolute minimum of evaluation necessary.